package homework;

import java.util.Arrays;
import java.util.Scanner;

public class sorttest {
//    //填坑法
//    public  static int sap(int []arr,int low,int high){
//        int tmp=arr[low];
//        while (low<high){
//            while(low<high&&tmp<=arr[high]){
//                high--;
//            }
//            arr[low]=arr[high];
//            while (low<high&&tmp>=arr[low]){
//                low++;
//            }
//            arr[high]=arr[low];
//        }
//        arr[low]=tmp;
//        return low;
//    }
//    //递归
//    public static void fast_sort6(int []arr,int low,int high){
//        if(low>=high){
//            return;
//        }
//        int pivot=sap(arr,low,high);
//        fast_sort6(arr,low,pivot-1);
//        fast_sort6(arr,pivot+1,high);
//
//    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[] arr= {78,98,2,50,1};

        sort1(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    private static void sort1(int[] arr, int s, int e) {
        if(s >= e){
            return;
        }
        int k = sap(arr , s ,e);
        sort1(arr,s,k-1);
        sort1(arr,k+1,e);
    }

    private static int sap(int[] arr, int s, int e) {
        int k = arr[s];
        while (s < e){
            while ( s < e && k <= arr[e]){
                e--;
            }
            arr[s] = arr[e];
            while ( s < e && k >= arr[s]){
                s++;
            }
            arr[e] = arr[s];
        }
        arr[s] = k;
        return s;
    }

}
